/*
** Copyright (C) 2009 Joshua Brent Marsh <joshua@icub3d.com>
**  
** This file is part of icub3d-adt
**
** icub3d-adt is free sofware; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 3 of the License, or
** (at your option) any later version.
**  
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
**  
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**  
*/

/* $Id: rbbtree_funcs.c 36 2009-11-02 15:06:50Z joshua@icub3d.com $ */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdlib.h>

#include "btree.h"
#include "btree_funcs.h"
#include "rbbtree_funcs.h"

struct btree_node * 
new_rbbtree_node (void *data, int color, struct btree_node *left,
	  struct btree_node *right)
{
  struct btree_node * new_node;

  /* we do the same as the btree version, except we set it's color as well. */
  
  new_node = malloc (sizeof (struct btree_node));
  if (new_node == NULL)
    {
      return NULL;
    }

  new_node->data = data;
  new_node->state = color;

  new_node->left = left;
  if (left != NULL)
    left->parent = new_node;

  new_node->right = right;
  if (right != NULL)
    right->parent = new_node;

  new_node->parent = NULL;
  
  return new_node;
}

int 
node_color (struct btree_node *node)
{
  if (node == NULL) /* NULL (leaf) nodes are black. */
    return RBBTREE_BLACK;
  else
    return node->state;
}

/* These are insert cases that make the logic for insertion easier. See:
   http://en.wikipedia.org/wiki/Red-black_tree#Operations for more information
   on what these do. */
void 
rbbtree_insert_case1 (Btree *btree, struct btree_node *cur)
{
  if (cur->parent == NULL)
    cur->state = RBBTREE_BLACK;
  else
    rbbtree_insert_case2(btree, cur);
}

void 
rbbtree_insert_case2 (Btree *btree, struct btree_node *cur)
{
  if (node_color (parent (cur)) != RBBTREE_BLACK)
    rbbtree_insert_case3 (btree, cur);
}

void 
rbbtree_insert_case3 (Btree *btree, struct btree_node *cur)
{
  if (node_color (uncle (cur)) == RBBTREE_RED)
    {
      parent (cur)->state = RBBTREE_BLACK;
      uncle (cur)->state = RBBTREE_BLACK;
      grandparent(cur)->state = RBBTREE_RED;

      rbbtree_insert_case1 (btree, grandparent (cur));
    }
  else
    rbbtree_insert_case4 (btree, cur);
}

void
rbbtree_insert_case4 (Btree *btree, struct btree_node *cur)
{
  if (cur == parent (cur)->right && parent (cur) == grandparent (cur)->left)
    {
      rotate_left (btree, cur->parent);
      cur = cur->left;
    }
  else if (cur == parent (cur)->left && 
	   parent (cur) == grandparent (cur)->right)
    {
      rotate_right (btree, parent (cur));
      cur = cur->right;
    }

  rbbtree_insert_case5 (btree, cur);
}

void 
rbbtree_insert_case5 (Btree *btree, struct btree_node *cur)
{
  parent (cur)->state = RBBTREE_BLACK;
  grandparent (cur)->state = RBBTREE_RED;

  if (cur == parent (cur)->left && parent (cur) == grandparent (cur)->left)
    rotate_right (btree, grandparent (cur));
  else
    rotate_left (btree, grandparent (cur));
}


/* These are removal cases that make the logic for removal easier. See:
   http://en.wikipedia.org/wiki/Red-black_tree#Operations for more information
   on what these do. */
void 
rbbtree_remove_case1 (Btree *btree, struct btree_node *cur)
{
  if (cur->parent != NULL)
    rbbtree_remove_case2 (btree, cur);
}

void
rbbtree_remove_case2 (Btree *btree, struct btree_node *cur)
{
  if (node_color (sibling (cur)) == RBBTREE_RED)
    {
      parent (cur)->state = RBBTREE_RED;
      sibling (cur)->state = RBBTREE_BLACK;
      
      if (cur == parent (cur)->left)
	rotate_left (btree, parent (cur));
      else
	rotate_right (btree, parent (cur));
    }

  rbbtree_remove_case3 (btree, cur);
}

void
rbbtree_remove_case3 (Btree *btree, struct btree_node *cur)
{
  if (node_color (parent (cur)) == RBBTREE_BLACK &&
      node_color (sibling (cur)) == RBBTREE_BLACK &&
      node_color (sibling (cur)->left) == RBBTREE_BLACK &&
      node_color (sibling (cur)->right) == RBBTREE_BLACK)
    {
      sibling (cur)->state = RBBTREE_RED;
      rbbtree_remove_case1 (btree, parent (cur));
    }
  else
    rbbtree_remove_case4 (btree, cur);
}

void 
rbbtree_remove_case4 (Btree *btree, struct btree_node *cur)
{
  if (node_color (parent (cur)) == RBBTREE_RED &&
      node_color (sibling (cur)) == RBBTREE_BLACK &&
      node_color (sibling (cur)->left) == RBBTREE_BLACK &&
      node_color (sibling (cur)->right) == RBBTREE_BLACK)
    {
      sibling (cur)->state = RBBTREE_RED;
      parent (cur)->state = RBBTREE_BLACK;
    }
  else
    rbbtree_remove_case5 (btree, cur);
}

void
rbbtree_remove_case5 (Btree *btree, struct btree_node *cur)
{
  if (cur == parent (cur)->left &&
      node_color (sibling (cur)) == RBBTREE_BLACK &&
      node_color (sibling (cur)->left) == RBBTREE_RED &&
      node_color (sibling (cur)->right) == RBBTREE_BLACK)
    {
      sibling (cur)->state = RBBTREE_RED;
      sibling (cur)->left->state = RBBTREE_BLACK;
      rotate_right (btree, sibling (cur));
    }
  else if (cur == parent (cur)->right &&
	   node_color (sibling (cur)) == RBBTREE_BLACK &&
	   node_color (sibling (cur)->right) == RBBTREE_RED &&
	   node_color (sibling (cur)->left) == RBBTREE_BLACK)
    {
      sibling (cur)->state = RBBTREE_RED;
      sibling (cur)->right->state = RBBTREE_BLACK;
      rotate_left (btree, sibling(cur));
    }

  rbbtree_remove_case6(btree, cur);
}

void 
rbbtree_remove_case6 (Btree *btree, struct btree_node *cur)
{
  sibling (cur)->state = node_color(parent (cur));
  parent (cur)->state = RBBTREE_BLACK;
  if (cur == parent (cur)->left) 
    {
      sibling (cur)->right->state = RBBTREE_BLACK;
      rotate_left(btree, parent (cur));
    }
  else
    {
      sibling (cur)->left->state = RBBTREE_BLACK;
      rotate_right(btree, parent (cur));
    }
}
